class Solution
{
public:
    // 优化后的贪心, 记录每次减去的数值和累计减去的数值, O(n)
    bool checkArray(vector<int> &nums, int k)
    {

        if (k == 1)
        {
            return true;
        }

        int n = nums.size();
        vector<int> dec(n, 0);
        int totalDec = 0;

        for (int i = 0; i < n - 1; ++i)
        {
            if (i - k >= 0)
            {
                totalDec -= dec[i - k];
            }
            if (totalDec > nums[i])
            {
                return false;
            }

            dec[i] = nums[i] - totalDec;
            totalDec += dec[i];
        }

        if (n - 1 - k >= 0)
        {
            totalDec -= dec[n - 1 - k];
        }
        return totalDec == nums[n - 1];
    }

    // 贪心法, 从第一个开始减. 最坏情况复杂度O(n^2), 会超时
    bool checkArray(vector<int> &nums, int k)
    {
        if (k == 1)
        {
            return true;
        }
        int n = nums.size();
        int i = 0;
        while (i <= n - k)
        {
            if (nums[i] == 0)
            {
                ++i;
                continue;
            }

            for (int j = i + 1; j < i + k; ++j)
            {
                if (nums[j] < nums[i])
                {
                    return false;
                }
                nums[j] -= nums[i];
            }
            nums[i] = 0;
        }

        while (i < n)
        {
            if (nums[i] != 0)
            {
                return false;
            }
            ++i;
        }

        return true;
    }
};